An official website of the United States government
Free, publicly-accessible full text available June 1, 2026
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
-
Abstract Gaussian random polytopes have received a lot of attention, especially in the case where the dimension is fixed and the number of points goes to infinity. Our focus is on the less-studied case where the dimension goes to infinity and the number of points is proportional to the dimensiond. We study several natural quantities associated with Gaussian random polytopes in this setting. First, we show that the expected number of facets is equal to$$C(\alpha)^{d+o(d)}$$, where$$C(\alpha)$$is some constant which depends on the constant of proportionality$$\alpha$$. We also extend this result to the expected number ofk-facets. We then consider the more difficult problem of the asymptotics of the expected number of pairs ofestranged facetsof a Gaussian random polytope. When the number of points is 2d, we determine the constantCsuch that the expected number of pairs of estranged facets is equal to$$C^{d+o(d)}$$.more » « lessFree, publicly-accessible full text available April 2, 2026
-
Free, publicly-accessible full text available December 10, 2025
-
Abstract A conjecture of Milena Mihail and Umesh Vazirani (Proc. 24th Annu. ACM Symp. Theory Comput., ACM, Victoria, BC, 1992, pp. 26–38.) states that the edge expansion of the graph of every polytope is at least one. Any lower bound on the edge expansion gives an upper bound for the mixing time of a random walk on the graph of the polytope. Such random walks are important because they can be used to generate an element from a set of combinatorial objects uniformly at random. A weaker form of the conjecture of Mihail and Vazirani says that the edge expansion of the graph of a polytope in is greater than one over some polynomial function of . This weaker version of the conjecture would suffice for all applications. Our main result is that the edge expansion of the graph of arandompolytope in is at least with high probability.more » « less
